// 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
// 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
// 来源：力扣（LeetCode）
// 链接：https://leetcode.cn/problems/word-break
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  if (s.length === 0) {
    return true
  }
  if (wordDict.length === 0) {
    return false
  }

  const wordSet = new Set()
  for (const word of wordDict) {
    wordSet.add(word)
  }

  const len = s.length
  const dp = new Array(len + 1).fill(false)

  dp[0] = true
  for (let idx = 1; idx <= len; idx++) {
    let flag = false
    for (const word of wordDict) {
      const curLen = word.length
      const curS = s.slice(idx - curLen, idx)
      if (idx - curLen < 0) {
        continue
      }
      const p = dp[idx - curLen] && wordSet.has(curS)
      if (p) {
        flag = true
        break
      }
    }

    dp[idx] = flag
  }

  return dp[len]
}

console.log(
  wordBreak('leetcode', ['leet', 'code'])
)







